public class Solution {
    public String countAndSay(int n) {
        if(n == 1) {
            return "1";
        }
        String[] ss = new String[n];
        ss[0] = "1";
        for(int i = 1; i < n; i++) {
            ss[i] = gen(ss[i - 1]);
        }
        return ss[n - 1];
    }

    private String gen(String s) {
        int len = s.length();
        StringBuilder sb = new StringBuilder();
        char c = s.charAt(0);
        int cn = 1;
        for(int i = 1; i < len; i++) {
            if(s.charAt(i) == c) {
                cn++;
            } else {
                sb.append(cn).append(c);
                cn=1;
                c = s.charAt(i);
            }
        }
        sb.append(cn).append(c);
        return sb.toString();
    }
}